package com.lw.leetcode.tree.b;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 307. 区域和检索 - 数组可修改
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/26 19:25
 */
public class NumArray {

    private int[] nums;

    private Node root;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.root = init(0, nums.length - 1);
    }

    public void update(int index, int val) {
        nums[index] = val;
        change(index, val, root);
    }

    public int sumRange(int left, int right) {
        int i = find(left, root);
        int j = find(right, root);
        return j - i + nums[left];
    }

    private int find (int index, Node node) {
        int end = node.end;
        if (end == index) {
            return node.sum;
        }
        int st = node.st;
        int m = st + ((end - st) >> 1);

        if (index <= m) {
            return find(index , node.left);
        }
        return node.left.sum + find(index, node.right);
    }


    private int change (int index, int val, Node node) {
        int st = node.st;
        int end = node.end;
        if (st == end) {
            node.sum = val;
            return val;
        }
        int m = st + ((end - st) >> 1);
        if (index <= m) {
            node.sum = node.right.sum + change(index, val, node.left);
        } else {
            node.sum = node.left.sum + change(index, val, node.right);
        }
        return node.sum;
    }

    private Node init(int st, int end) {
        Node node = new Node(st, end);
        if (st == end) {
            node.sum = nums[st];
            return node;
        }

        int m = st + ((end - st) >> 1);
        Node left = init(st, m);
        node.sum =  left.sum;
        node.left = left;
        Node right = init(m + 1, end);
        node.sum += right.sum;
        node.right = right;
        return node;
    }

    class Node {

        public Node(int st, int end) {
            this.st = st;
            this.end = end;
        }

        private int st;

        private int end;

        private int sum;

        private Node left;

        private Node right;
    }

}
